//
// Created by grainlee on 16/9/12.
//

#include <iostream>
#include <vector>

using namespace std;
vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> res;
    sort(nums.begin(),nums.end());
    for (int i = 0 ; i < nums.size()-1; i++){
        if (i > 0 && nums[i] == nums[i-1]) continue;
        int j,k,target;
        target = 0 - nums[i];
        j = i+1;
        k = nums.size() -1;

        while (j < k){
            if ( j > i+1 && nums[j] == nums[j-1]){
                j++;
                continue;
            }
            if (k < nums.size()-1 && nums[k] == nums[k+1]){
                k--;
                continue;
            }
            if ((nums[j] + nums[k]) > target){
                k--;
            } else if ((nums[j] + nums[k]) < target){
                j++;
            } else{
                vector<int> tmp;
                tmp.push_back(nums[i]);
                tmp.push_back(nums[j]);
                tmp.push_back(nums[k]);
                res.push_back(tmp);
                j++;
            }
        }
    }
    return res;
}

int main(){

}
